

/**
* 插入排序：把待排序的元素，按照起关键码的值的大小，逐个插入到一个已经排好序的有序序列中
直到所有的元素都插入完毕为止。从而得到一个有序序列。
*/

// 1. 直接插入排序
public void insertSort(int[] array) {
	
	if (array == null || array.length == 0) return;
	
	// 用 i 遍历整个数组
	for (int i = 1; i < array.length; i++) {
		// j 下标为 i 下标前一个
		int j = i - 1;			
		// 记录 i 下标当前的元素
		int tmp = array[i];
		for (j = i - 1; j >= 0; j--) {

			if (array[j] > tmp) {
				// 如果 array[j] 的值大于 tmp 
				// 则将 array[j] 的位置移出来
				array[j + 1] = array[j];
			} else {
				break;
			}
		}
		// j+1 位置就是最小元素的下标
		array[j + 1] = tmp;
	}
}

public void insertSortRange(int[] array, int start,int end) {
	
	if(array == null || array.length == 0) return;
	if(start >= end || start < 0 || right >= array.length) return;
	
	for (int i = start + 1; i < end; i++) {
		int j = i - 1;
		int tmp = array[i];
		for (j = i - 1; j >= left; j--){
			if (array[j] > tmp) {
				array[j + 1] = array[j];
			} else {
				break;
			} 
		}
		array[j + 1] = tmp;
	}
}
//分析直接插入排序：
// 最好情况：数据完全有序，时间复杂度为 O(N)
// 最坏情况：数据完全无序，时间复杂度为 O(N^2)
// ==> 
// 结论：当所给的数据，有序程度越高，则该方法的排序速度就越快
// 一般在一组基本有序的数据中，进行使用~~
// 空间复杂度：O(1)
// 稳定性：稳定

// 2.希尔排序（缩小增量排序）
// 先选定一个整数，把待排序数组中的元素分成多个组（距离为那个整数值的元素分在同一个组中）
// 并对每一组的元素进行排序，然后再取一个整数，重复进行分组和排序
// 当取的整数值达到 1 的时候，所有的记录在同一组内排好序
public void shellSort(int[] array) {
	
	int gap = array.length;
	
	while (gap > 1) {
		gap /= 2;
		shell(array, gap);
	}
}

// 希尔排序的本质是插入排序的一种优化方式。不过是 i 和 j 的运动
// 由之前的一个一个变化，变成了跳跃的 gap
public void shell(int[] array, int gap) {
	
	for(int i = gap; i < array.length; i++) {
		// 注意：以 gap 距离进行分组
		// j = i - gap
		int j = i - gap;
		// 将 tmp 定义在外层循环中
		int tmp = array[i];
		
		// j 每次移动 gap ==》 j -= gap
		for (j = i - gap; j >= 0; j-= gap) {
			if (array[j] > tmp) {
				array[j + gap] = array[j];
			} else {
				break;
			}
		}
		array[j + gap] = tmp; 
	}
}

//===============================================================

/**
 选择排序： 每一次从待排序的数据元素中选出一个最大 / 最小的元素，放在序列的起始位置
          直到所有数据排序完毕
*/

// 直接选择排序
// 初始状态：整个数组分为有序区和无序区 初始时有序区为空，无序区包含数组的所有元素
// 第一轮选择：在无序区中找到最小的元素，将他与无序区的第一个元素交换位置
// 			 此时有序区包含一个元素，无序区包含 n - 1 个元素
// 重复上述过程
public void selectSort(int[] array) {
	
	if (array == null || array.length == 0) return;
	
	// i 表示当前已排序区间的末尾索引（初始为 0，即未排序）
	// 每轮循环后，i 位置都会被填入【未排序区间】的最小元素
	// 当 i 从 0 递增到 array.length - 1 最终整个数组就是有序区间
	for (int i = 0; i < array.length; i++) {
		int minIndex = i;
		for (int j = i + 1; j < array.length; j++) {
			if (array[j] < array[minIndex]) {
				minIndex = j;
			}
		}
		swap(array, minIndex, i);
	}
}

private void swap(int[] array, int i, int j) {
	int tmp = array[i];
	array[i] = array[j];
	array[j] = tmp;
}

// 直接选择排序的优化版本：增加 maxIndex 这样一次循环下来，能同时找到最小值和最大值

public void selectSort2(int[] array) {
	int left = 0;
	int right = array.length - 1;
	
	while (left < right) {
		
		int minIndex = left;
		int maxIndex = left;
		
		for (int i = left + 1; i <= right; i++) {
			if (array[i] < array[minIndex]) minIndex = i;
			if (array[i] > array[maxIndex]) maxIndex = i;
		}
		swap(array,minIndex,left);
		
		// 当最大元素的初始值的下标，正好为 left 的时候
		// left 和 minIndex 的值进行交换
		// 此时 maxIndex 指向的值就不是最大值了，进行修正~~
		if (maxIndex == left) {
			maxIndex = minIndex;
		}
		swap(array,maxIndex,right);
		left++;
		right--;
	}
}

/**
 直接选择排序分析：
      时间复杂度：没有最好和最坏情况，都是 O(N^2)
	  空间复杂度：O(1)
	  稳定性：不稳定
*/

//===================================================================


// 堆排序，排升序需要建立大根堆，降序建立小根堆
// 先构建大根堆，然后再循环交换堆顶元素与末尾元素，同时调整堆结构
// 直到数组成为升序
public void heapSort(int[] array) {
	createBigHeap(array);
	int end = array.length - 1;
	while (end > 0) {
		swap(array, 0, end)
		// 执行完 swap 后，堆顶元素（索引 0）被替换成了原末尾的元素
		// 此时堆顶的新元素可能会破坏大根堆的结构，因此需要从根节点开始向下调整
		// 确保整个堆重新满足大根堆的性质
		shiftDown(array,0,end);
		end--;
	}
}

// 构建大根堆，从最后一个非叶子节点开始，从后往前，对每个父节点执行“向下调整”
// 最终使得数组满足大根堆特性
private void createBigHeap(int[] array) {
	
	for (int parent = ((array.length -1 -1) / 2); parent >= 0; parent--) {
		shiftDown(array, parent, array.length);
	}
	
}

// 向下调整堆，给定父亲节点索引，找到左右孩子中较大的那个，若孩子的值大于父节点的值则交换
// 然后递归调整子节点
private void shiftDown(int[] array, int parent, int end) {
	int child = 2 * parent + 1;
	while (child < end) {
		if (child + 1 < end && array[child] < array[child + 1]) {
			child++; // 这里是让 child 指向两个孩子节点中，值较大的哪一个
		}
		if (array[child] > array[parent]) {
			swap(array, child, parent);
			parent = child;
			child = 2 * parent + 1;
		} else {
			break;
		}
	}
}

/*
补充：在 createBigHeap 中，parent 的值从后向前--，但 heapSort 中的 shiftDown 直接是从 0 到 end 进行调整
本质上是因为两者的目的和场所不相同
createBigHeap 是为了将无序数组整体构建为大根堆，从最后一个非叶子节点开始，从后往前，进行调整
堆的结构中，叶子节点因为没有子节点，本身就满足父节点大于子节点的性质，所以不需要调整
最后一个非叶子节点的索引是 ( array.length -2 ) / 2 . 从这个索引开始向前调整
就能覆盖所有需要调整的父节点

heapSort 是在每次交换完堆顶后，修复未排序部分的节点，从堆顶开始，向下维护堆
*/
/**
* 时间复杂度：O(n*lgn) ==> 构建大根堆的时间复杂度为O(n) 每次 shiftDown 的时间复杂度为O(lgn) （堆的高度为 lgn)
  空间复杂度：O(1)
  稳定性：不稳定
*/




// ===================================================================

/**
交换排序：通过反复比较序列中两个元素的大小，若他们的相对顺序不符合要求，则交换位置
        通过多次这样的比较和交换操作，逐步将元素调换到正确我i之
核心操作：比较 -- 交换
*/

//冒泡排序
public void bubbleSort(int[] array) {
	
	// i 为比较的趟数
	for (int i = 0; i < array.length; i++) {
		boolean flg = false; // 定义flg表示是否发生交换
		// j 为一趟中比较的次数
		for (int j = 0; j < array.length - 1 - i; j++) {
			if (array[j] > array[j + 1]) {
				swap(array, j, j + 1);
				flg = true;
			}
		}
		if (flg == false) {
			return;
		}
	}
}

/** 
冒泡排序：
时间复杂度：O(N^2)
通过添加 flg 进行优化之后，最好的情况为 O(N)
空间复杂度：O(1)
稳定性：稳定
*/

// =========================================================================



// 快速排序
// 思想，二叉树结构的交换排序方法。任意取排序元素中的某元素作为基准值，按照基准值，将排序集合分割成两个子序列。
// 左子序列中的所有元素均小于基准值，右子序列中的所有元素均大于基准值。
// 然后在左右序列中重复该过程，直到所有元素都排在相应位置上。

public void quickSort(int[] array) {
	quick(array,0,array.length - 1);
}

private void quick(int[] array, int start, int end) {
	if (start >= end) return;
	
	int pivot = partition(array, start, end);
	
	quick(array, start, pivot - 1);
	quick(array, pivot + 1, end);
}

// Hoare 版快排逻辑：
private int partition(int[] array, int left, int right) {
	int key = array[left];
	// 用 i 来保存基准值的位置
	int i = left;
	
	while (left < right) {
		while (left < right && array[right] >= key) {
			right--; 
		}
		// 经过上面的 while 循环，right 一定在后面指向第一个小于 key 的下标
		
		while (left < right && array[left] <= key) {
			left++;
		}
		// 经过上面的 while 循环，left 一定在前面指向第一个大于 key 的下标
		
		swap(array,left,right);
	}
	// 结束 while(left<right)循环后，left 和 right 最终在汇合在一起
	// 此时 left 和 right 的汇合位置就是基准值应该的下标
	
	swap(array,i,left);
	return left;
}

/** 需要注意两点：
* 	1.在指针移动过程中，右指针先进行移动，是为了可以保证：当双指针相遇的时候
  相遇位置的元素，一定小于等于基准值（因为右指针停止的时候，指向的是 小于 key 的元素）
  此时将基准值与相遇位置交换，能确保基准值左侧均 <= key，右侧均 >= key

	2. 在比较条件中，使用的是 >= 和 <= ，而不是单纯的 > 和 <。
	这样的目标是，允许重复元素被跳过，避免双指针在遇到 key 相等的元素时候被卡住
	例如 [2,2,3]，使用 > / < 会导致指针无法移动
*/
/**
   时间复杂度：
	从分区函数（partition）的时间复杂度和整体递归结构两方面入手
	分区函数的作用是对长度 n(n=right-left+1)的子数组进行分区，时间复杂度为O(N)
	快速排序整体的时间复杂度：最好情况：O(N logN) ==> 每次分区都能将数组分为大致相等的两部分
						  最坏情况：O(N^2) ==> 每次分区都会成为极不平衡的两部分
				空间复杂度：最好情况：O(logN) 满二叉树
						  最坏情况：O(N) 单分支树
*/



// =============================================================

//挖坑法
/**
  挖出一个一个坑，会首先将 key 的值单独存起来（相当于挖了一个坑）
  然后从 right 开始找比 key 小的元素，找到后，把索引的值填入key 下标索引中（之前挖的坑中）
*/
private int partition2(int[] array, int left, int right) {
	
	// 挖第一个坑
	int key = array[left];
	
	while (left < right) {
		while (left < right && array[right] >= key) {
			right--;
		}
		// 填坑 同时再挖新的坑
		array[left] = array[right];
		
		while (left < right && array[left] <= key) {
			left++;
		}
		// 填坑，同时再挖新的坑
		array[right] = array[left];
	}
	// 将最开始挖坑的值填进去
	array[left] = key;
	return left;
}
//=============================================================

// 前后指针法
private int partition3(int[] array,int left, int right) {
	int prev = left; // prev 用来标记小于基准区域的右边界
	int cur = prev + 1; // 用 cur 来遍历数组
	
	while (cur <= right) {
		//array[left] 为基准值
		// array[++prev] != array[cur] 的作用是：
		// 当 prev 移动后指向的元素与 cur 指向的元素相同时，跳过交换操作，避免无效交换
		
		if (array[cur] < array[left] && array[++prev] != array[cur]) {
			swap(array,ur,prev);
		}
		cur++;
	}
	swap(array,prev, left);
	return prev;
}

// ========================================================
/**
  无论是 Hoare 法，挖坑法，还是前后指针法，都会出现单分支树的最坏情况 ==》 
  导致栈溢出
  优化：
  栈溢出，就是树的高度太高了，需要栈的空间太多
  优化==》
  降低需要的树的高度 ==》
  尽量的使单分支树变为满 / 完全二叉树
*/

// 快速排序优化：三数取中法：
private int midOfThree(int[] array, int left,int right) {
	int mid = (left + right) / 2;
	if (array[left] < array[right] {
		if (array[mid] <array[left]) {
			return left;
		} else if(array[mid] > array[right] {
			return right;
		} else {
			return mid;
		}
	} else { // array[left] >= array[right]
		if (array[mid] < array[right]) {
			return right;
		} else if(array[mid] > array[left] {
			return left;
		} else {
			return mid;
		}
	}
}

// 优化1.在 quicSort 中使用三数排中法
private void quick(int[] array, int start, int end) {
	
	if(start >= end) {
		return;
	}
	
	int index = midOfThree(array,start,end);
	swap(array, start, index);
	
	int pivot = partition(array,start,end);
	quick(array, start, pivot)
	quick(array,pivot + 1,end);
}

// 优化2：在递归创建的时候，最后两层所占用的空间是最多的
// 在快速排序中，是利用树的递归思想在不断进行排序的，递归到后面比较小的子区间的时候
// 大致已经有序了
// 又知道，直接插入排序在对大致有序的数组中进行排序的时候，效率较高
// ==》
// 所以，可以在进行快速爱旭过程中，递归到比较小的区间的时候，使用插入排序
public void quickSort(int[] array) {
	quick(array, 0, array.length - 1);
}
private void quick(int[] array, int start, int end) {
	if (start >= end) return;
	
	// 当需要排序的元素个数小于15 个元素，可以使用直接插入排序
	if (end - start+ 1 <= 15) {
		insertSortRange(array, start,end);
		return;
	}
	
	// ...
}

// 非递归实现快速排序
public void quickSortNor(int[] array) {
	Stack<Integer> stack = new Stack<>();
	int left = 0;
	int right = array.length - 1;
	
	int pivot = partition(array, left, right);
	if (pivot - 1 >left) { // 确保左侧能放入两个元素
		// 先压入左，再压入右
		stack.push(left);
		stack.push(pivot - 1);
	}
	if (pivot + 1 < right){
		stack.push(pivot + 1);
		stack.push(right);
	}
	
	while (!stack.isEmpty()){
		// 弹的时候，先弹右边，再弹左边
		right = stack.pop();
		left = stack.pop();
		pivot = partition(array, left, right);
		if (pivot - 1 > left) {
			stack.push(left);
			stack.push(pivot - 1);
		}
		if (pivot + 1 < right) {
			stack.push(pivot + 1);
			stack.push(right);
		}
	}
}

// ====================================================

/**
 归并排序基本思想：
 建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个典型应用
 将已有的子序列合并，得到完全有序的序列。
 若将两个有序表合并成一个有序表 ==》 二路归并
*/

// 归并排序
public void mergeSort(int[] array) {
	mergeSortFun(array, 0, array.length - 1);
}

private void mergeSortFun(int[] array, int left, int right) {
	
	// 递归分解
	if (left >= right) return;
	
	int mid = (left + right) / 2;
	
	mergeSortFun(array, left, mid);
	mergeSortFun(array, mid + 1, right);
	
	// 合并
	
	merge(array,left,right,mid);
}

private void merge(int[] array, int left, int right, int mid) {
	
	// s1 和 s2 分别是两个序列段的开始位置
	int s1 = left;
	int s2 = mid + 1;
	// right - left + 1 是计算两个序列段的元素个数
	int[] tmpArr = new int[right - left + 1];
	int k = 0;
	while (s1 <= mid && s2 <= right) { // 确保两个数组都有元素
		if(array[s2] < array[s1]) {
			tmpArr[k] = array[s2];
			s2++;
			k++;
		} else {
			tmpArr[k] = array[s1];
			k++;
			s1++;
		}
	}
	// 其中有一个数组没有元素 
	while (s1 <= mid) {
		tmpArr[k] = array[s1];
		s1++;
		k++;
	}
	while (s2 <= right) {
		tmpArr[k] = array[s2];
		s2++;
		k++;
	}
	
	// tmpArr 已经是有序数组 将其拼接在 arr 上
	for (int i = 0; i < tmpArr.length;i++) {
		// 注意拼接时候，array 的下标为 i + left，避免覆盖
		array[i + left] = tmpArr[i];
	}
}

/**
 归并排序中，时间复杂度始终为 O(n*logN)
*/


// =========================================

/**
 其他非依据比较排序 （了解~~）
*/

// 计数排序，又称鸽巢原理，
// 操作步骤：
// 		1. 统计相同元素出现的次数
//		2. 根据统计的结果，将序列进行回收~
// 这里需要解决的问题是，第一步需要申请一个计数数组，来对统计后的记过进行回收
// 那这个数组的当都该如何确定 ==》 可以用序列段的最大值 max - 最小值 min + 1 来确定数组的长度
// 注意，这个申请的数组是用来统计数据出现的个数的！！！

public void countSort(int[] array) {
	int minVal = array[0];
	int maxVal = array[0];
	// 将序列段中值最大和最小的元素获得
	for (int i = 0; i < array.length; i++) {
		if (array[i] < minVal) {
			minVal = array[i];
		}
		if (array[i] > maxVal) {
			maxVal = array[i];
		}
	}
	
	int[] countArr = new int[maxVal-minVal+1];
	
	// 遍历原数组，统计每个元素出现的次数
	for( int i = 0; i < array.length; i++) {
		int count = array[i]; //例如 count得到值为90
		// 为了让 90 映射到 0 ==》 让 90 - 90 可以实现映射
		// count-minVal 是为了可以实现映射~
		countArr[count - minVal]++;
	}
	
	// 遍历 countArr 数组，把元素写回 array
	int index = 0; // 重新表示 array 数组的下标
	for (int i = 0; i < countArr.length;i++) {
		while (countArr[i] > 0){
			array[index] = i+minVal;
			countArr[i]--;
			index++;
		}
	}
}
